package org.example.myleet.p942;

/**
 * 贪心证明：遇到I时，填入集合中未选的最小的数，遇到D时，填入集合中未选的最大的数
 * 这样可以一直保证：出现I时，都是下一个数比当前的数大，出现D时，都是下一个数比当前的数小
 */
public class Solution {
    public int[] diStringMatch(String s) {
        char[] charArr = s.toCharArray();
        int n = charArr.length;
        //左指针代表集合中未选的最小的数，右指针代表集合中未选的最大的数
        int l = 0, r = n;
        int[] result = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            char c = charArr[i];
            if (c == 'I') {
                //I时，填入左指针的数，并右移左指针
                result[i] = l;
                ++l;
            } else {
                //D时，填入右指针的数，并左移左指针
                result[i] = r;
                --r;
            }
        }
        result[n] = l;
        return result;
    }
}
